/**
 * Author  zxy
 * Date  2023/8/15 10:46
 */

import java.util.HashMap;
import java.util.Map;

class LRUNode<K, V> {
    K key;
    V value;
    LRUNode<K, V> prev;
    LRUNode<K, V> next;

    public LRUNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, LRUNode<K, V>> cache;
    private LRUNode<K, V> head;
    private LRUNode<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new LRUNode<>(null, null);
        this.tail = new LRUNode<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        LRUNode<K, V> node = cache.get(key);
        if (node != null) {
            removeLRUNode(node);
            addToFront(node);
            return node.value;
        }
        return null;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            LRUNode<K, V> node = cache.get(key);
            node.value = value;
            removeLRUNode(node);
            addToFront(node);
        } else {
            if (cache.size() >= capacity) {
                cache.remove(tail.prev.key);
                removeLRUNode(tail.prev);
            }
            LRUNode<K, V> newLRUNode = new LRUNode<>(key, value);
            cache.put(key, newLRUNode);
            addToFront(newLRUNode);
        }
    }

    private void removeLRUNode(LRUNode<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(LRUNode<K, V> node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "one");
        lruCache.put(2, "two");
        lruCache.put(3, "three");

        System.out.println(lruCache.get(1));  // Output: one

        lruCache.put(4, "four");  // Cause eviction of key 2

        System.out.println(lruCache.get(2));  // Output: null (evicted)
    }
}
